#include<iostream>
#include<vector>
using namespace std;
struct TreeNode {
         int val;
         TreeNode *left;
         TreeNode *right;
         TreeNode() : val(0), left(nullptr), right(nullptr) {}
         TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
         TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
        };
    // vector<vector<int>> zigzagLevelOrder(TreeNode* root) 
    // {
    //     //双数组

    // }


    int findBottomLeftValue(TreeNode* root) {
        //我们使用层序遍历
        vector<TreeNode*> cur = {root};
        vector<TreeNode*> next;
        vector<vector<int>> ans;
        while(cur.size())
        {
            vector<int> vals;
            for(auto node : cur)
            {
                vals.push_back(node -> val);
                if(node-> left) next.push_back(node -> left);
                if(node -> right) next.push_back(node -> right);
            }
            cur = next;
            next.clear();
            ans.push_back(vals);
        }
        int size = ans.size() - 1;
        int ret = ans[size].front();
        return ret;
    }
int main()
{
    return 0;
}